Database systems are often designed to maintain large amounts of information about a variety of entities, events, etc. The items about which a database maintains information may possess a variety of characteristics. Even database systems that do not yet contain large amounts of information are often designed to be scalable such that the database systems can be adapted to accommodate large amounts of information.
It is common for each row in a table to correspond to a single item. For example, each row in a table may correspond to a distinct sale. It is possible for the row about an item to have columns for every characteristic associated with the item. Thus, the row about a sale could have a column that stores the amount of the sale, the date of the sale, the store at which the sale occurred, the street address of that store, the city in which the store resides, the state in which the store resides, the item involved in the sale, the department to which the item belongs, the manager of that department, etc. However, storing all of the characteristics of an item within the row for the item results in an enormous amount of duplication. For example, the city and state of each store would be duplicated in the row for every sale made by that store. To avoid such duplication, the row for a particular item may merely include a key to a row of another table that has further information about the item. For example, the row for a particular sale may simply have a store_id, where the store_id is a key to separate table that has a row for each store and addition information about each store (e.g. city, state, etc.). A schema in which one table (a “fact table”) has one row per item, where the row for each item includes keys to one or more other tables (dimension tables) that contain characteristics of the item, is referred to as a star schema.
Aggregation queries that are run against data that is organized in a star schema typically specify a join key, and a grouping key. The join key determines which row in a dimension table should be combined with a given row in the fact table. For example:
select * from F, D
where F.city_id=D.city_id
group by D.state.
This query indicates that each row in fact table F should be joined with the row in dimension table D that has the same value for “city” as the fact table row. Further, once the rows from the fact table are joined to the appropriate rows in the dimension table, the rows should be divided into groups based on state.
In many cases, there is a many-to-one relationship between rows in a fact table and rows in a dimension table. That is, based on the join key, there is no more than one row in the dimension table with which any given fact table row will join. However, that is not always the case. In situations where a single row from the fact table may join with multiple rows in the dimension table, the database server must be able to perform many-to-many join and aggregation operations. For example, assume that information about sales per geographical location and additional information about the geographical location is split between a sales table (the fact table) and a geography table (a dimension table). The sales table comprises information about sales of a product and names of cities where the sales occur and the geography table comprises information about cities, and states and countries within which they are located.
Two or more states may have cities with the same name. Consequently, in the geography table, multiple rows may have the same city name (with different state and/or country values). For example, Pennsylvania, Colorado, Kansas, Illinois, Michigan and North Dakota all have cities named Erie. Thus, five rows of the geography table may have the city name ‘Erie’ and the value in the “state” column for each of the five rows will be a different state name from states Pennsylvania, Colorado, Kansas, Illinois, Michigan and North Dakota. The geography table may also have city names of other cities in those five states associated with their respective states. Under these circumstances, assume that the sales table has one or more rows where the city name is “Erie”. Each of those rows will have its respective sales amount. Under these circumstances, when the join key is “city”, rows in the fact table will have a many-to-many relationship relative to the rows with which they join in the dimension table. Therefore, any query that specifies a join and/or aggregation operation between the sales table and the geography table, where the join key is “city”, requires a database server to process a many-to-many join and/or aggregation operations for data of sales and geography tables.
One current approach for performing many-to-many join and aggregation operations is to perform a hash join using hash tables. A “hash join” operation, generally speaking, comprises two phases. In the first phase, known as the “build phase,” the database server generates a hash table by hashing each row of the first table according to a hash function on the join column(s). In the second phase, known as the “probe phase,” the database server then iteratively scans through each row of the second table. For each row in the second table, the database server uses the hash function and the hash table to identify rows in the first table with equivalent join column values. When matching rows are identified, the rows are merged and added to the result set for the join operation, assuming the rows also match any applicable join predicates. One technique for performing hash join operations is described in U.S. Pat. No. 8,825,678, issued Sep. 2, 2014, the contents of which are incorporated herein by reference.
When both tables in the join operation are relatively large, the database server may be unable to fit a hash table for the entire first table into memory. In such situations, the tables may be partitioned and the database server may perform nested loops with respect to the partitions. However, the two phased approach remains essentially the same during each iteration of the loop. Thus, using hash tables to perform many-to-many join operations in this manner is inefficient as it requires a significant amount of memory. Therefore, database systems that contain large amounts of information suffer significant performance degradation when performing many-to-many join and aggregation operations.